package main

import (
	"fmt"
)

func main() {
	arr := []int{1, 9, 4, 2, 5, 7, 8}
	tree := build(arr)
	fmt.Println(tree.query(1, 6))	//查询1到6的区间和
	tree.upData(0, 100)			//下标为0的值加 100
	tree.upData(6, -1)			//下标为6的值减 1
	fmt.Println(tree.query(0, 5))	//查询0到5的区间和
}
/*
	树状数组操作(单点更新, 区间查询)
*/
type Tree struct {
	t []int
	length int
}
func build(arr []int) *Tree {
	length := len(arr)
	tree := &Tree{make([]int, length+1), length+1}
	tree.init(arr)
	return tree
}
func (this *Tree)init(arr []int) { //O(n)建树
	for i, j := 1, 0; i<this.length; i++ {
		this.t[i] += arr[i-1]
		j = i + lowBit(i); if j < this.length {this.t[j] += this.t[i]}
    }
}
func (this *Tree)upData(x, v int) {for x++; x < this.length; x+=lowBit(x) {this.t[x]+=v}}
func (this *Tree)pre(x int) (ans int){for ; x > 0; x-=lowBit(x) {ans += this.t[x]}; return}
func (this *Tree)query(l, r int) int {return this.pre(r+1)- this.pre(l)}
func lowBit(x int) int {return x&-x}